package Tree;

import java.util.Stack;

/**
 * 题目 ：所有大于或等于节点的值之和
 * 题目详述 :
 * 给定一个二叉搜索树，请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。
 *
 * 提醒一下，二叉搜索树满足下列约束条件：
 * 节点的左子树仅包含键 小于 节点键的节点。
 * 节点的右子树仅包含键 大于 节点键的节点。
 * 左右子树也必须是二叉搜索树。
 */
public class ConvertBST {
    /**
     * 核心思想 ：
     * 由于二叉搜索树通过中序遍历所遍历到的节点是从小到大进行排序的；
     * 即，当遍历到你自身节点时，前面所遍历到的节点都是比你节点自身要小的节点；同时后面所要遍历的节点也都是比你节点自身要大的节点；
     * （1）方法一 ：
     * 先遍历一遍二叉搜索树（无论何种遍历方式），获取到所有节点之和total；
     * 然后使用中序遍历二叉搜索树中每个节点，在正在遍历的节点之前被遍历的节点之和，即为所有比当前节点值小的节点值之和minSum；
     * 最后，通过计算，即total - minSum，运算得到所有大于或者等于当前节点的值之和；
     * （2）方法二 ：
     * 由于常规的中序遍历是 左子树 - 根节点 - 右子树 ，这样子的遍历顺序；
     * 根据二叉搜索树的特性，即使用非常规的中序遍历 ： 右子树 - 根节点 - 左子树；
     * 当遍历到当前节点的话，之前所遍历的节点皆为比当前节点大的节点；同时后序所要遍历的节点也皆为比当前节点小的节点
     * @param root
     * @return
     */
    public TreeNode convertBST(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        int sum = 0;
        while(node != null || !stack.isEmpty()){
            // 首先，遍历根节点的右子树
            while(node != null){
                stack.push(node);
                node = node.right;
            }
            // 若是所遍历到节点为null的话，需要去将node节点得到stack栈中的节点
            node = stack.pop();
            // sum = 右序遍历之和（即，右子树 - 根节点 - 左子树）
            sum += node.val;
            // 当前节点值进行替换；
            node.val = sum;
            // 后续遍历，根节点的左子树
            node = node.left;
        }
        return root;
    }
}
